/*
 * @Author: w
 * @Date: 2022-02-22 22:13:16
 * @Description: 剑指 Offer 04. 二维数组中的查找
 */

// 标志树、线性查找 （排序数组的 二分法不是优解）

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */

// 递归+二分查找 （还未AC）
var findNumberIn2DArray = function (matrix, target, i = 0) {
  const arr = matrix[i];
  if (arr[0] <= target <= arr[arr.length - 1]) {
    if (bs(arr, target)) {
      return true;
    } else {
      return findNumberIn2DArray(matrix, target, ++i);
    }
  } else {
    return false;
  }
};

var bs = function (arr, t) {
  let left = 0,
    right = arr.length - 1;
  let mid = Math.floor(arr.length / 2);
  while (true) {
    if (arr[mid] < t) {
      left = mid;
      mid = Math.floor(right - left / 2);
    } else if (arr[mid] > t) {
      right = mid;
      mid = Math.floor(right - left / 2);
    } else {
      return mid;
    }
  }
};

// es6 语法
var findNumberIn2DArray = function (matrix, target) {
  const arr = matrix.flat();
  return arr.includes(target);
};
